package com.zjj.algorithm.learning.leetcode.tree;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 404. 左叶子之和 简单题
 * 给定二叉树的根节点 root ，返回所有左叶子之和。
 * <p>
 * 输入: root = [3,9,20,null,null,15,7]
 * 输出: 24
 * 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 * 示例 2:
 * <p>
 * 输入: root = [1]
 * 输出: 0
 *
 * @author zjj_admin
 * @date 2022/11/23 10:39
 */
public class SumOfLeftLeaves {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        /**
         *                          node1(1)
         *                  node2(2)       node3(3)
         *           node4(4)    node5(5)
         *                          node6(6)
         */

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node5.left = node6;

        int res = sumOfLeftLeaves(node1);
        System.out.println("res = " + res);
    }


    /**
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 39.4 MB
     * 击败
     * 43.98%
     *
     * @param root
     * @return
     */
    public static int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 0;
        }
        //定义一个队列用于存放节点
        Deque<TreeNode> queue = new ArrayDeque<>();
        //将根节点放入队列
        queue.addLast(root);
        int sum = 0;
        while (!queue.isEmpty()) {
            //取出队列第一个元素
            TreeNode node = queue.removeFirst();
            // 当这点的左子节点不为空时
            if (node.left != null) {
                //判断做子节点是否存在叶子节点
                if (node.left.left == null && node.left.right == null) {
                    //当左子节点不存在叶子节点时，说明这个左子节点就是一个左叶子节点，需要求和
                    sum += node.left.val;
                } else {
                    //不是叶子节点时，戒左叶子节点添加到队列即可
                    queue.addLast(node.left);
                }

            }
            //当这个节点的右子节点不为 null 时，就添加到队列中
            if (node.right != null) {
                queue.addLast(node.right);
            }
        }
        return sum;
    }
}
